/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * https://leetcode.cn/problems/permutations/
 * 思路：画出树状图，分析递归
 */
class Permute {
    List<List<Integer>> ret=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int len=nums.length;
        boolean[] uesd=new boolean[len];
        Deque<Integer> qu=new LinkedList<>();
        permute(nums,uesd,qu,len,0);
        return ret;
    }
    public void permute(int[] nums,boolean[] uesd,Deque<Integer> qu,int len,int depth){
        if(depth==len){
            ret.add(new ArrayList<>(qu));
        }
        for(int i=0;i<len;i++){
            if(!uesd[i]){
                uesd[i]=true;
                qu.addLast(nums[i]);  
                permute(nums,uesd,qu,len,depth+1);
            uesd[i]=false;
            qu.removeLast(); 
            }
            
        }
    }
}